package algorithms.question.class23;

import common.util.MyUtil;

import java.util.HashSet;
import java.util.Set;

/**
 * 定义什么是可整合数组：
 * 一个数组排完序之后，除了最左侧的数外，有arr[i] = arr[i-1]+1
 * 则称这个数组为可整合数组
 * 比如{5,1,2,4,3}、{6,2,3,1,5,4}都是可整合数组
 * 返回arr中最长可整合子数组的长度
 *
 * @author guichang
 * @date 2021/8/30
 */

@SuppressWarnings("all")
public class Code3_最长可整合子数组的长度 {
    // 可整合概念：
    // 1、不重复
    // 2、max-min = 个数-1


    public static void main(String[] args) {
        int[] nums = MyUtil.createArray(6, 2, 3, 1, 5, 4);
        MyUtil.print(maxIntegrableLength(nums));
    }

    /**
     * TODO 实现有问题
     * @param nums
     * @return
     */
    public static int maxIntegrableLength(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 结果
        int res = 1;
        // 用户判断是否存在重复元素
        Set<Integer> set = new HashSet<>();
        // 记录最大值和最小值
        int max = 0, min = 0;
        for (int i = 0; i < nums.length; i++) {
            set.clear();
            for (int j = i; j < nums.length; j++) {
                // 第一个元素直接处理
                if (set.size() == 0) {
                    max = nums[i];
                    min = nums[i];
                    set.add(nums[i]);
                    continue;
                }
                // 判断违规1：重复元素
                if (set.contains(nums[j])) {
                    res = Math.max(res, set.size());
                    break;
                }
                // 增加
                max = Math.max(max, nums[j]);
                min = Math.min(min, nums[j]);
                set.add(nums[j]);
                // 判断违规2：max-min = 个数-1
                if (max - min != set.size() - 1) {
                    res = Math.max(res, set.size() - 1);
                    break;
                }
            }
        }
        return res;

    }

}